//有一个有 n 个节点的有向图，节点按 0 到 n - 1 编号。图由一个 索引从 0 开始 的 2D 整数数组 graph表示， graph[i]是与节点 
//i 相邻的节点的整数数组，这意味着从节点 i 到 graph[i]中的每个节点都有一条边。 
//
// 如果一个节点没有连出的有向边，则它是 终端节点 。如果没有出边，则节点为终端节点。如果从该节点开始的所有可能路径都通向 终端节点 ，则该节点为 安全节点 
//。 
//
// 返回一个由图中所有 安全节点 组成的数组作为答案。答案数组中的元素应当按 升序 排列。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//输入：graph = [[1,2],[2,3],[5],[0],[5],[],[]]
//输出：[2,4,5,6]
//解释：示意图如上。
//节点 5 和节点 6 是终端节点，因为它们都没有出边。
//从节点 2、4、5 和 6 开始的所有路径都指向节点 5 或 6 。
// 
//
// 示例 2： 
//
// 
//输入：graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
//输出：[4]
//解释:
//只有节点 4 是终端节点，从节点 4 开始的所有路径都通向节点 4 。
// 
//
// 
//
// 提示： 
//
// 
// n == graph.length 
// 1 <= n <= 10⁴ 
// 0 <= graph[i].length <= n 
// 0 <= graph[i][j] <= n - 1 
// graph[i] 按严格递增顺序排列。 
// 图中可能包含自环。 
// 图中边的数目在范围 [1, 4 * 10⁴] 内。 
// 
// Related Topics深度优先搜索 | 广度优先搜索 | 图 | 拓扑排序 
//
// 👍 352, 👎 0 
//
//
//
//

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class FindEventualSafeStates {
    public static void main(String[] args) {
        Solution solution = new FindEventualSafeStates().new Solution();
        solution.eventualSafeNodes(new int[][]{{1, 2}, {2, 3}, {5}, {0}, {5}, {}, {}});
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 拓扑排序 + 反向图
        /*public List<Integer> eventualSafeNodes(int[][] graph) {
            int m = graph.length;
            // 入度数组
            int[] indegree = new int[m];
            LinkedList<Integer>[] graphList = new LinkedList[m];
            for (int i = 0; i < m; i++) {
                graphList[i] = new LinkedList<>();
            }

            // 将有向图反向
            for (int i = 0; i < graph.length; i++) {
                int[] g = graph[i];
                for (int to : g) {
                    graphList[to].add(i);
                    indegree[i]++;
                }
            }

            // 入度为0的节点入度
            Queue<Integer> queue = new LinkedList<>();
            for (int i = 0; i < m; i++) {
                if (indegree[i] == 0) queue.offer(i);
            }

            while (!queue.isEmpty()) {
                Integer cur = queue.poll();
                for (int next : graphList[cur]) {
                    indegree[next]--;
                    if (indegree[next] == 0) {
                        queue.offer(next);
                    }
                }
            }

            // 获取所有入度为0的节点
            List<Integer> res = new LinkedList<>();
            for (int i = 0; i < indegree.length; i++) {
                if (indegree[i] == 0) res.add(i);
            }

            return res;
        }*/

        // DFS + 三色标记法
        // 若起始节点位于一个环，或者能到达一个环，那么该节点就是不安全的。否则该节点是安全的。
        // 白色（用 0 表示）：该节点尚未被访问；
        // 灰色（用 1 表示）：该节点位于递归栈中，或者在某个环上；
        // 黑色（用 2 表示）：该节点搜索完毕，是一个安全节点。

        int[][] graph;

        public List<Integer> eventualSafeNodes(int[][] graph) {
            this.graph = graph;
            List<Integer> res = new LinkedList<>();
            int[] color = new int[graph.length];
            for (int i = 0; i < graph.length; i++) {
                // 如果不是环，满足条件
                if (dfs(i, color)) res.add(i);
            }

            return res;
        }

        // 三色法判断是否是环
        public boolean dfs(int cur, int[] color) {
            // 如果大于0，判断是否是遍历过的节点，也就是visited数组
            if (color[cur] > 0) return color[cur] == 2;
            // 赋值为正在遍历，也就是onPath数组
            color[cur] = 1;
            for (int next : graph[cur]) {
                if (!dfs(next, color)) {
                    return false;
                }
            }
            // 遍历之后，回溯为2
            color[cur] = 2;
            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}
